// 思路： 将一个元素插入到已排序的序列中，插入后仍然有序
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
// 稳定性：稳定
// 适用场景：数据量较小
// 不适用于数据量较大的情况
function insertionSort(arr) {
    for(let i = 1; i < arr.length; i++) {
        let temp = arr[i]
        let j = i
        while(j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1];
            j--
        }
        arr[j] = temp
    }
    return arr
}

const arr = [5, 3, 8, 4, 2];
console.log(insertionSort(arr));